<HTML>

<HEAD>

<LINK rel="stylesheet" href="../exer.css">

</HEAD>

<BODY>

<H1>

Data Structures, Algorithms, & Applications in C++<BR>

Chapter 9, Exercise 7<BR>

<BR>

</H1>





The code for <code class=var>MinHeap</code> is given below and in the file

<code class=var>minheap.h</code>.









<HR class = coderule>

<pre class = code>

template&lt;class T&gt;

class MinHeap {

   public:

      MinHeap(int MinHeapSize = 10);

      ~MinHeap() {delete [] heap;}

      int Size() const {return CurrentSize;}

      T Min() {if (CurrentSize == 0)

                  throw OutOfBounds();

               return heap[1];}

      MinHeap&lt;T&gt;&amp; Insert(const T&amp; x);

      MinHeap&lt;T&gt;&amp; DeleteMin(T&amp; x);

      void Initialize(T a[], int size, int ArraySize);

      void Deactivate() {heap = 0;}

   private:

      int CurrentSize, MaxSize;

      T *heap; // element array

};



template&lt;class T&gt;

MinHeap&lt;T&gt;::MinHeap(int MinHeapSize)

{// Min heap constructor.

   MaxSize = MinHeapSize;

   heap = new T[MaxSize+1];

   CurrentSize = 0;

}



template&lt;class T&gt;

MinHeap&lt;T&gt;&amp; MinHeap&lt;T&gt;::Insert(const T&amp; x)

{// Insert x into the min heap.

   if (CurrentSize == MaxSize)

      throw NoMem(); // no space



   // find place for x

   // i starts at new leaf and moves up tree

   int i = ++CurrentSize;

   while (i != 1 &amp;&amp; x &lt; heap[i/2]) {

      // cannot put x in heap[i]

      heap[i] = heap[i/2]; // move element down

      i /= 2; // move to parent

      }

   heap[i] = x;



   return *this;

}



template&lt;class T&gt;

MinHeap&lt;T&gt;&amp; MinHeap&lt;T&gt;::DeleteMin(T&amp; x)

{// Set x to min element and delete

 // min element from heap.

   // check if heap is empty

   if (CurrentSize == 0)

      throw OutOfBounds(); // empty



   x = heap[1]; // min element



   // restucture heap

   T y = heap[CurrentSize--]; // last element



   // find place for y starting at root

   int i = 1,  // current node of heap

       ci = 2; // child of i

   while (ci &lt;= CurrentSize) {// find place to put y

      // heap[ci] should be larger child of i

      if (ci &lt; CurrentSize &amp;&amp;

          heap[ci] &gt; heap[ci+1]) ci++;



      // can we put y in heap[i]?

      if (y &lt;= heap[ci]) break;  // yes



      // no

      heap[i] = heap[ci]; // move child up

      i = ci;  // move down a level

      ci *= 2;

      }

   heap[i] = y;



   return *this;

}



template&lt;class T&gt;

void MinHeap&lt;T&gt;::Initialize(T a[],

                 int size, int ArraySize)

{// Initialize min heap to array a.

   delete [] heap;

   heap = a;

   CurrentSize = size;

   MaxSize = ArraySize;



   // make into a min heap

   for (int i = CurrentSize/2; i &gt;= 1; i--) {

      T y = heap[i]; // root of subtree



      // find place to put y

      int c = 2*i; // parent of c is target

                   // location for y

      while (c &lt;= CurrentSize) {

         // make c point to larger sibling

         if (c &lt; CurrentSize &amp;&amp;

             heap[c] &gt; heap[c+1]) c++;



         // can we put y in heap[c/2]?

         if (y &lt;= heap[c]) break;  // yes



         // no

         heap[c/2] = heap[c]; // move heap[c] up

         c *= 2;              // move c down a level

         }

      heap[c/2] = y;

      }

}

<hr class=coderule>

</pre>

<br><br>





</FONT>

</BODY>

</HTML>

